#include <bits/stdc++.h>
#pragma once
using namespace std;

namespace fuh{
    template <class K,class V>
    struct HashNode{
        HashNode<K,V>* n_next;
        pair<K,V> n_kv;    
        HashNode(const pair<K,V> & kv = pair<K,V>())
        :n_kv(kv)
        ,n_next(nullptr)
        {

        }
    };
    template <class Key>
    struct DefaultHashfunc{
        size_t operator()(const Key& k){
              return (size_t)k;
        }
    };
    template<>
    class DefaultHashfunc<string>{
        size_t operator()(const string &s)
        {
            //BKDR
            size_t hashVal = 0;
            for(auto&ch:s)
            {
                hashVal*=31;
                hashVal+=ch;
            }
            return hashVal;
        }
    };
    template<class Key,class Val,class HashFunc = DefaultHashfunc<Key>>    
    class HashTableBuket
    {
        typedef HashNode<Key,Val> Node;
        typedef HashNode<Key,Val>* NodePtr;
        vector<NodePtr> m_ht;
        size_t m_size= 0;
        HashFunc m_hsc;
        bool Insert(NodePtr cur)
        {
            if(!cur)
            {
                return 0;
            }
            size_t Index = m_hsc(cur->n_kv.first)%m_ht.size();
            cur->n_next = m_ht[Index];
            m_ht[Index] = cur;
            m_size++;
            return 1;
        }
        public:
        HashTableBuket(size_t size = 10)
        :m_size(0)
        ,m_ht(size,nullptr)
        {

        }
        ~HashTableBuket()
        {
            for(size_t i=0;i<m_ht.size();i++)
            {
                NodePtr cur = m_ht[i];
                while(cur)
                {
                    NodePtr tmp = cur;
                    cur = cur->n_next;
                    delete tmp;
                }
                m_ht[i] = nullptr;
            }
        }

        bool insert(const pair<Key,Val>& kv){
            if(find(kv.first))
            {
                return false;
            }
            checkSize();
            size_t Index = m_hsc(kv.first)%m_ht.size();

            //front_insert
            NodePtr cur = new Node(kv);
            cur->n_next = m_ht[Index];
            m_ht[Index] = cur;
            m_size++;
            return 1;
        }
        
        void checkSize()
        {
            if(m_size==m_ht.size())
            {
                HashTableBuket<Key,Val,HashFunc> NewHT(m_ht.capacity()*2);
                for(size_t i =0;i<m_ht.size();i++)
                {
                    NodePtr cur = m_ht[i];
                    m_ht[i] = nullptr;
                    if(i==4)
                    {
                        int b = 0;
                    }
                    while(cur)
                    {
                        NodePtr tmp = cur;
                        cur = cur->n_next;
                        NewHT.Insert(tmp);
                    }
                }
                NewHT.m_ht.swap(m_ht);
            }
        }
        NodePtr find(const Key& key)
        {
            size_t Index = m_hsc(key)%m_ht.size();
            NodePtr cur = m_ht[Index];
            while(cur)
            {
                if(cur->n_kv.first==key)
                {
                    return cur;
                }
                cur = cur->n_next;
            }
            return nullptr;
        }
        bool erase(const Key& k)
        {
            size_t Index = m_hsc(k);
            NodePtr cur = m_ht[Index];
            if(cur && cur->n_kv.first==k)
            {
                m_ht[Index] = cur->n_next;
                delete cur;
                cur = nullptr;
                return 1;
            }
            while(cur && cur->n_next)
            {
                if(cur->n_next->n_kv.first ==k)
                {
                    NodePtr tmp = cur->n_next;
                    cur->n_next = tmp->n_next;
                    delete tmp;
                    return true;
                }
                cur = cur->n_next;
            }
            return false;
        }
        void print()
        {
            for(size_t i =0;i<m_ht.size();i++)
            {
                NodePtr cur = m_ht[i];
                std::cout<<i<<"->:";
                while(cur)
                {
                    std::cout<<cur->n_kv.first<<" ";
                    cur = cur->n_next;
                }
                std::cout<<std::endl;
            }
            cout<<endl;
        }
    };

};